W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Dany jest zbiór liczb całkowitych . Dla i całkowitych, , przedziałem nazywamy zbiór kolejnych liczb całkowitych od do : . Rozbiciem zbioru na przedziały nazywamy taki ciąg parami rozłącznych przedziałów, że suma tych przedziałów daje zbiór .
Twoim zadaniem jest napisać losowy generator rozbić zbioru na przedziały. Generator będzie działał w sposób iteracyjny. W danym momencie pamiętamy zbiór liczb całkowitych, które są w , a nie zostały użyte jeszcze w żadnym przedziale. Zaczynamy od całego zbioru . Następnie w każdej iteracji losujemy jakiś przedział i usuwamy go ze zbioru. Postępujemy tak dopóki pamiętany zbiór nie jest pusty.
Losowanie przedziału należy wykonać jak następuje. Mamy pewien podzbiór zbioru . Oznaczmy go przez . Wylosowany przedział musi się zawierać w . Numerujemy wszystkie przedziały, które się zawierają w , od zera w kolejności leksykograficznej względem początku i końca przedziału. Np. dla kolejne przedziały to: i mają one odpowiednio numery . Wybór przedziału dokonujemy przez wylosowanie numerka. Numerek losuje sprawdzaczka.
Twój program powinien działać według następującego schematu. Najpierw należy wczytać jedną liczbę całkowitą , . Następnie należy zainicjować . Teraz, dopóki , należy wykonywać kolejne iteracje. W pojedynczej iteracji należy:
Dla danych wejściowych:
5 6 2 0
poprawną odpowiedzią jest:
15 2 3 4 4 5 1 1 1
Autor zadania: Jakub Pawlewicz.